class Solution:
    def mctFromLeafValues(self, arr: list) -> int:
        dp = [[2**31 for _ in range(len(arr))] for _ in range(len(arr))]
        for j in range(len(arr)):
            for i in range(j, -1, -1):
                if i == j:
                    dp[i][j] = 0
                    continue
                if j - i == 1:
                    dp[i][j] = arr[i] * arr[j]
                    continue
                for k in range(i, j):
                    dp[i][j] = min(
                        max(arr[i:k + 1]) * max(arr[k + 1:j + 1]) + dp[i][k] +
                        dp[k + 1][j], dp[i][j])

        return dp[0][-1]
